This invention relates generally to social networking, and in particular to creating clusters of a user's connections in a social networking system.
A social networking system allows users to designate other users as connections by forming relationships with other users or otherwise indicating an association with one or more other users. Users can then contribute and interact with media items, use applications, join groups, list and confirm attendance at events, create pages, and perform other tasks that facilitate social interaction with their connections. In a social networking system, a user may have a very large number of connections, and these connections may be drawn from a variety of different experiences in the user's real life. For example, a user may have a number of connections from school, other connections from work, and still other sets of connections that form various different social circles.
In certain applications in the social networking system, it may be desirable to cluster a user's connections into groups of other people who are themselves within common social circles. A cluster of connections for a user may reflect common characteristics of the connections based on their affinity to each other. This may facilitate, for example, inviting a user's connections to an event so that the invitees generally know each other. The clusters of connections can be selectively blocked or promoted to the user depending on, among other factors, the user settings, context, common characteristics of the clusters, and the user's affinity with the members of the cluster. In particular, automatically clustering a user's connections satisfied the user's need for varying privacy settings on the user's different interactions. The social networking system may also alleviate the burden on the user to go through a potentially large number of connections to find one or more of them.
Some social networking systems allow users to form manual clusters, where a user directly places the user's connections into predetermined groups or lists of friends. But manual clustering can be very time consuming, and many users are unlikely to make the effort to make clusters of their friends manually. Moreover, a user may not be in the best position to know the interrelationships among that user's connections and therefore would not be able to form accurate clusters of the user's connections who are themselves in common social circles. These limitations may result in a subpar user experience when navigating through a large number of connections and trying to group those connections into coherent groups of friends. Given the limitations on creating accurate clusters of friends, concerns about privacy may also prevent the user from interacting with the social networking to the same extent as where the user knows that a specified set of actions will be visible only to certain clusters of the user's connections.
Existing algorithms for clustering are not amenable to computation on an as needed basis. The relationships between connections in a social networking system change rapidly, and to run computationally intensive algorithms on the entire social graph is a challenge. Moreover, manual methods for creating clusters of connection have several drawbacks, as explained above.